#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdbool.h>
struct ListNode {
	int val;
	struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{
	if (!head)
		return NULL;
	struct ListNode* fast = head, * slow = head;
	while (fast)
	{
		if (!fast->next)
			return slow;
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
	if (head == NULL)
	{
		return NULL;
	}
	struct ListNode* cur = head;
	struct ListNode* next = head->next;
	struct ListNode* newhead = NULL;
	while (cur)
	{
		cur->next = newhead;
		newhead = cur;
		cur = next;
		if (next)
			next = next->next;
	}
	return newhead;
}
bool chkPalindrome(struct ListNode* A) {
	struct ListNode* mid = middleNode(A);
	struct ListNode* otherhead = reverseList(mid);
	struct ListNode* cur = A, * other = otherhead;
	while (other) {
		if (cur->val != other->val)
		{
			return false;
		}
		cur = cur->next;
		other = other->next;
	}
	return true;
}